# -*- coding: utf-8 -*-

# 问题描述：
# 给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表
# 你可以假设除了数字 0 之外，这两个数字都不会以零开头

# 示例：
# 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
# 输出：7 -> 0 -> 8
# 原因：342 + 465 = 807

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        carry = 0;
        rtn = current_node = None;
        while l1 and l2:
            sum_val = l1.val + l2.val + carry;
            carry = sum_val / 10;
            if current_node == None:
                rtn = ListNode(sum_val % 10);
                current_node = rtn;
            else:
                current_node.next = ListNode(sum_val % 10);
                current_node = current_node.next;
            l1 = l1.next;
            l2 = l2.next;

        while l1:
            sum_val = l1.val + carry;
            carry = sum_val / 10;
            current_node.next = ListNode(sum_val % 10);
            l1 = l1.next;
            current_node = current_node.next;

        while l2:
            sum_val = l2.val + carry;
            carry = sum_val / 10;
            current_node.next = ListNode(sum_val % 10);
            l2 = l2.next;
            current_node = current_node.next;

        if carry != 0:
            current_node.next = ListNode(1);

        return rtn;


number_list_1 = ListNode(1);
# number_list_1.next = ListNode(4);
# number_list_1.next.next = ListNode(3);

number_list_2 = ListNode(9);
number_list_2.next = ListNode(9);
# number_list_2.next.next = ListNode(4);

t = Solution();
node = t.addTwoNumbers(number_list_1, number_list_2);
while node:
    print node.val;
    node = node.next;








# # 阅读官方提供的答案
# public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
#     ListNode dummyHead = new ListNode(0);
#     ListNode p = l1, q = l2, curr = dummyHead;
#     int carry = 0;
#     while (p != null || q != null) {
#         int x = (p != null) ? p.val : 0;
#         int y = (q != null) ? q.val : 0;
#         int sum = carry + x + y;
#         carry = sum / 10;
#         curr.next = new ListNode(sum % 10);
#         curr = curr.next;
#         if (p != null) p = p.next;
#         if (q != null) q = q.next;
#     }
#     if (carry > 0) {
#         curr.next = new ListNode(carry);
#     }
#     return dummyHead.next;
# }

# # 学习到的内容：
# ListNode dummyHead = new ListNode(0);
# ......
# return dummyHead.next;
# 使用链表的时候，首先生成一个不具有真实作用的头结点dummyHead，然后返回结果的时候直接跳过次无效节点
# 这样能够减少一个头结点为空的判断